home *** CD-ROM | disk | FTP | other *** search
/ Games of Daze / Infomagic - Games of Daze (Summer 1995) (Disc 1 of 2).iso / x2ftp / msdos / wgt / wgttut1 / poly.txt < prev    next >
Encoding:
Text File  |  1994-10-07  |  9.2 KB  |  252 lines
  1.               WGT Graphics Tutorial #1
  2.                Topic: Filled Polygons
  3.              By Chris Egerter
  4.              October 7, 1994
  5.  
  6. Introduction
  7. ------------
  8.    This series of tutorials describes a method of drawing filled polygons
  9. using 3 rendering techniques: Solid, Gouraud shading, and texture mapping.
  10.  
  11. The code in this tutorial was written in Turbo C++ but can be ported to
  12. other graphics libraries and operating systems.  I did not use the
  13. WGT functions in this one, so the wgtgfx.c file contains a few routines
  14. which are needed for the demo.  I have decided to explain the method
  15. used for these routines since I had to discover them on my own, and
  16. think you can learn from the code.
  17.  
  18. 1.0 - What is a Polygon?
  19. ------------------------
  20.     To start things off, we should first define what a polygon is.  A
  21. polygon is a any figure that is composed of straight lines. It can have any
  22. number of sides, and may or may not be closed.  We will be discussing closed
  23. polygons in this article mainly because they allow you to fill the interior
  24. with a colour. An open polygon can only have its edges drawn because there
  25. is no difference between the inside and outside.  Furthermore, we will
  26. only discuss convex polygons.  If you draw a horizontal line across the
  27. polygon, it must cross exactly two edges at any given vertical position.
  28. If the polygon passes this test, it is convex.
  29.  
  30.  
  31. 2.0 - Drawing Polygons with Horizontal Lines
  32. --------------------------------------------
  33.     In computer graphics, the screen is comprised of an x and a y axis,
  34. with the coordinate (0,0) being the top left corner.  Each polygon consists
  35. of a number of vertices, each of which contain an (x,y) coordinate on the
  36. screen.  Our first task is to draw a filled polygon given a set of vertices.
  37. A simple way to fill the polygon would be to draw lines between the vertices
  38. (making sure to connect the first to the last) and using a region fill
  39. routine to fill in the interior.  This works in most cases however it is
  40. slow, and not very useful in a program that requires animation.  The other
  41. method, is to draw a series of horizontal lines that make up the polygon.
  42.  
  43. 3.0 - The algorithm
  44. -------------------
  45.     The reason for dealing with only convex polygons is simple.  Knowing
  46. that we can draw the polygon using horizontal lines, we can simply store
  47. the starting and ending x coordinate of the horizontal line on each y
  48. coordinate of the polygon.  Non-convex polygons would require several
  49. horizontal lines per y coordinate, and things get a bit more complicated.
  50.  
  51.     Our basic algorithm for drawing polygons is this:
  52. 1. Calculate the starting and ending x coordinate of the horizontal line
  53.    on each y coordinate.  We can do this by using a standard line algorithm
  54.    but instead of plotting pixels, store the x coordinates into an array.
  55.    Simply calculate the lines between all vertices and connect the first
  56.    and last vertex with a line to close the figure.
  57. 2. Draw each horizontal line given the row, and two columns.
  58.  
  59.     As you can see here, a polygon may be drawn using two simple, well
  60. known routines: The line (with any slope), and the horizontal line.
  61.  
  62.  
  63. 4.0 - Keeping Track of the Left and Right Edges
  64. -----------------------------------------------
  65.     Let's define two arrays which will contain our horizontal line
  66. coordinates. These routines assume you are using 320x200x256 graphics mode,
  67. however they can be easily ported to another mode by changing the 200 to the
  68. number of rows the mode has.
  69.  
  70. int startx[200];
  71. int endx[200];
  72.  
  73.     Before the polygon is drawn, each value in these arrays will be set
  74. to an impossible number to indicate that no point has been found on that y
  75. coordinate.  For the following examples, I will use -16000 as the impossible
  76. number that would never be used.
  77.  
  78.  
  79. 5.0 - Scan Converting the Edges of the Polygon
  80. ----------------------------------------------
  81.     Our next step is to create a routine that will calculate a line and
  82. store the x coordinates for every y coordinate.  When we store the x
  83. coordinate, first check the startx array.  If it is -16000, this is the
  84. first point found on this row.  We will then store the x coordinate into
  85. the startx array and continue with the line.  If startx is not -16000, this
  86. means a point has already been found, and we can store the coordinate in the
  87. endx array (since we already know each row has exactly two intersections with
  88. the polygon).
  89.  
  90. Below is the code for this routine:
  91.  
  92. void polyline (int x1, int y1, int x2, int y2)
  93. /* Calculates the coordinates of a line given two
  94.    vertices (x1,y1) an (x2,y2).
  95.  
  96.    We will use fixed point math to speed things up.
  97.    The x coordinate is multiplied by 256 and for each row,
  98.    a constant m is added to x.  This is a simplified version
  99.    of a line algorithm because we only have to store 1 x coordinate
  100.    for every y coordinate.
  101.  
  102. */
  103. {
  104.  int tmp,y;
  105.  long x,m;
  106.  
  107.  if (y2 != y1)     /* This isn't a horizontal line */
  108.  {
  109.    if (y2 < y1)    /* Make sure y2 is greater than y1 */
  110.    {
  111.     tmp = y1;      /* Swap the y coordinate */
  112.     y1 = y2;
  113.     y2 = tmp;
  114.  
  115.     tmp = x1;      /* Swap the corresponding x coordinates */
  116.     x1 = x2;
  117.     x2 = tmp;
  118.    }
  119.  
  120.  x = (long)x1<<8;  /* Multiply be 256 */
  121.  
  122.  m = ((long)(x2 - x1)<<8) / ((long)(y2 - y1));
  123.  /* m is the fractional amount to add to the x coordinate every row.
  124.     m is equal to (delta x) / (delta y).  In other words, the x coordinate
  125.     has to change by (x2 - x1) columns in (y2 - y1) rows. */
  126.  
  127.  x += m; /* We ALWAYS skip the first point in every line. This is done */
  128.  y1++; /* because we do not want to store the point where two lines
  129.       meet, twice.  This would result in a single point being drawn. */
  130.  
  131.  for (y = y1; y <= y2; y++) /* Go through each row */
  132.   {
  133.    if ((y >= 0) & (y < 200)) /* If the coordinate is on the screen */
  134.     if (startx[y] == -16000) /* Store the first coordinate */
  135.       startx[y] = x>>8;
  136.     else
  137.       endx[y] = x>>8;        /* Store the last coordinate */
  138.    x += m;                   /* Add our constant to x */
  139.    }
  140.  }
  141. }
  142.  
  143.  
  144. 6.0 - Calling the Polyline Routine
  145. ----------------------------------
  146.     Next we need to write a routine that will go through our vertex list
  147. and call this routine.  Once that is complete, we can draw all of our
  148. horizontal lines.
  149.  
  150.     First of all, let's make a structure for our vertices.
  151. This segment should appear at the top of your program with the startx and
  152. endx arrays.
  153.  
  154. typedef struct
  155.     {
  156.      int x,y;
  157.     } point;
  158.  
  159.     Our main polygon routine will take an array of points, call the
  160. polyline routine between each of the points, and finally draw each
  161. horizontal line in the array.
  162.  
  163. Below is the filled polygon main routine:
  164.  
  165. void fillpoly (point *vertexlist, int numvertex)
  166. /* Draws a filled polygon given an array of vertices. */
  167. {
  168. int i;
  169. point *curpt,*nextpt;
  170.   /* Two pointers to a vertex. These are used to connect to vertices
  171.      together in when calling the polyline routine. */
  172.  
  173.  curpt = vertexlist;      /* Set to the first vertex in the array */
  174.  nextpt = vertexlist + 1; /* and to the second vertex */
  175.  
  176.  for (i = 0; i < 200; i++)
  177.   {
  178.    startx[i] = -16000;     /* Set up our impossible values */
  179.    endx[i] = -16000;
  180.   }
  181.  
  182.  for (i = 1; i < numvertex; i++)
  183.   {
  184.    polyline (curpt->x, curpt->y, nextpt->x, nextpt->y);
  185.    /* Calculate the edge of this line. */
  186.  
  187.    curpt += 1;  /* Go to the next line */
  188.    nextpt += 1;
  189.   }
  190.  
  191.   nextpt = vertexlist;  /* Now close the polygon by doing a line between
  192.                the first and last vertex. */
  193.   polyline (curpt->x, curpt->y, nextpt->x, nextpt->y);
  194.  
  195.   for (i = 0; i < 200; i++)   /* Now draw the horizontal line list */
  196.     if (startx[i] != -16000)  /* Indicates there is a line on this row */
  197.     {
  198.      if (endx[i] == -16000)
  199.      endx[i] = startx[i]; /* In case there was only one
  200.                  point found on this row */
  201.        line (startx[i], i, endx[i], i);
  202.        /* Draw a line between the two x coordinates, on the row i. */
  203.     }
  204. }
  205.  
  206.  
  207. Now we should make a small test program to use these functions:
  208.  
  209. point mypoints[10];
  210.  
  211. void main (void)
  212. {
  213.  initialize_graphics ();
  214.  
  215.  mypoints[0].x = 160;
  216.  mypoints[0].y = 30;
  217.  mypoints[1].x = 50;
  218.  mypoints[1].y = 150;
  219.  mypoints[2].x = 270;
  220.  mypoints[2].y = 180;
  221.  
  222.  fillpoly (&mypoints, 3);
  223.  getch ();
  224.  close_graphics ();
  225. }
  226.  
  227.     This will draw a triangle in the middle of the screen.
  228. You can use these routines with any graphics library.  The only routines
  229. you will need to rename are the graphics initialization and closing routines,
  230. and the line routine.
  231.  
  232.     That's are there is to it.  This is a simple case however. There are
  233. other methods to fill a polygon with something other than solid colours. The
  234. two techniques I will discuss in the next issues are Gouraud shading and
  235. texture mapping.
  236.  
  237. The code and test program contained in this text file has been put into
  238. two files:
  239.  
  240. fillpoly.c  - contains the original (portable) code
  241. poly256.c   - contains a demonstration in the 320x200x256 graphics mode
  242.  
  243. wgtgfx.c    - Various graphics support routines 
  244. wgtgfx.h    - Header file for support routines
  245.  
  246. poly256 has been compiled into poly256.exe so you can view what these
  247. routines do instantly.  To compile poly256, make a project file and
  248. compile and link poly256.c and wgtgfx.c together.
  249.  
  250.  
  251.  
  252.